# -*- coding: utf-8 -*-
import random
import numpy as np
import pandas as pd
from deap import algorithms, base, creator, tools
from timeit import default_timer as timer
import multiprocessing

"""
派单问题转换为单个手艺人的TSP问题
手艺人的顺序基因形式形如：
[1,3,2,4,8,6,5,7,9]
"""

df_artisans = pd.read_csv('data/sample/artisans.csv', nrows=50)
df_orders = pd.read_csv('data/sample/orders.csv', nrows=200)
df_times = pd.read_csv('data/sample/travel_times.csv')
# 定义基因长度为订单总数
indSize = len(df_artisans)

# Create Fitness and Individual Classes
creator.create('FitnessMax', base.Fitness, weights=(1.0,))
creator.create('Individual', list, fitness=creator.FitnessMax)
toolbox = base.Toolbox()


def get_travel_time(order, p1, start):
    p2 = str(order['lon']) + ',' + str(order['lat'])
    try:
        travel_times = df_times[(df_times['p1'] == p1) & (df_times['p2'] == p2)]
        travel_times['start_time'] = travel_times['start_time'].apply(lambda x: int(x) - int(start))
        best_time = travel_times['start_time'].abs().sort_values()[0]
    except:
        best_time = 0
    return best_time


def artisan_tsptw(artisan_ids):
    """
    根据手艺人编号，求解手艺人TSP问题
    :param artisan_id: 手艺人编号
    :return:
    """
    global df_orders
    artisan_orders = dict()
    remain_orders = list(df_orders.index)
    total_time = 0
    for artisan_id in artisan_ids:
        if artisan_id in artisan_orders:
            pre_order_id = artisan_orders[artisan_id][-1]
            pre_order = df_orders.iloc[pre_order_id]
        else:
            # 如果是该手艺人第一单
            pre_order = df_artisans.iloc[artisan_id-1]
        next_order = None
        pre_stop_time = int(pre_order['stop'])
        # print('get pre_stop_time: ' + str(pre_stop_time))
        if pre_order is not None:
            p1 = str(pre_order['lon']) + ',' + str(pre_order['lat'])
            # 排除时间冲突的订单
            df_artisan_orders = df_orders[(df_orders.index.isin(remain_orders)) & (df_orders['start'] >= pre_stop_time)]
            # print('get df_artisan_orders: ' + str(len(df_artisan_orders)))
            try:
                df_artisan_orders['travel_time'] = df_artisan_orders.apply(get_travel_time, axis=1, args=(p1, pre_stop_time))
                df_artisan_orders = df_artisan_orders[df_artisan_orders['start'] >= df_artisan_orders['travel_time'] + pre_stop_time]
                next_order = df_artisan_orders.sort_values('travel_time').head(1)
            except Exception as e:
                print(e)
        if next_order is not None:
            next_index = next_order.index[0]
            if artisan_id in artisan_orders:
                artisan_orders[artisan_id].append(next_index)
            else:
                artisan_orders[artisan_id] = [next_index]
            try:
                remain_orders.remove(next_index)
            except:
                print('remain_oders has no index: ' + next_index)
            # 注意此处订单时间包含了与上单的间歇时间 + 路程时间
            next_order_time = int(next_order['stop']) - int(pre_stop_time)
            total_time += next_order_time
    # 还有订单未分配完
    if len(remain_orders) > 0:
        total_time = None
    return total_time


def eval_vrptw(individual):
    """
    进化过程
    :param individual: 个体对象
    :param instance: 个体相关数据
    :return:
    """
    print('check genes: ' + str(individual))
    total_time = artisan_tsptw(individual)
    if total_time is not None:
        fitness = 1.0 / total_time
    else:
        fitness = 0
    return fitness,


def ga_vrptw(ind_size, pop_size, cx_pb, mut_pb, gen_size):
    """
    遗传算法主程序
    :param ind_size: 基因长度
    :param pop_size: 种群数量
    :param cx_pb: 交叉概率
    :param mut_pb: 变异概率
    :param gen_size: 进化次数
    :return:
    """
    # 生成基因序列
    # 从手艺人编号中随机选取分派给订单
    toolbox.register('indexes', random.sample, range(1, ind_size + 1), ind_size)
    # 生成独立个体
    toolbox.register('individual', tools.initIterate, creator.Individual, toolbox.indexes)
    # 生成初始的种群
    toolbox.register('population', tools.initRepeat, list, toolbox.individual)
    # Initialize the population
    pop = toolbox.population(n=pop_size)
    # Operator registering
    toolbox.register('evaluate', eval_vrptw)
    toolbox.register('select', tools.selRoulette)
    # toolbox.register('mate', cx_partialy_matched)
    # toolbox.register('mutate', mut_inverse_indexes)
    toolbox.register('mate', tools.cxPartialyMatched)
    toolbox.register('mutate', tools.mutShuffleIndexes, indpb=mut_pb)

    # Begin the evolution
    # hof = tools.HallOfFame(1)
    # stats = tools.Statistics(lambda ind: ind.fitness.values)
    # stats.register("avg", np.mean)
    # stats.register("std", np.std)
    # stats.register("min", np.min)
    # stats.register("max", np.max)
    # pop, log = algorithms.eaSimple(pop, toolbox, cxpb=cx_pb, mutpb=mut_pb, ngen=gen_size, stats=stats, halloffame=hof, verbose=True)
    # return pop, log

    g = 0
    fitnesses = list(toolbox.map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit
    fits = [ind.fitness.values[0] for ind in pop]
    # 第一代种群中 未找到有效派单方案
    if len(fits) == 0:
        return "no feasible solution found, please increase population size."
    while len(fits) > 0 and g < gen_size:
        # A new generation
        g = g + 1
        print("-- Generation %i --" % g)
        # Select the next generation individuals
        offspring = toolbox.select(pop, len(pop))
        # Clone the selected individuals
        offspring = list(map(toolbox.clone, offspring))
        # Apply crossover and mutation on the offspring
        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            # cross two individuals with probability CXPB
            if random.random() < cx_pb:
                toolbox.mate(child1, child2)
                # fitness values of the children
                # must be recalculated later
                del child1.fitness.values
                del child2.fitness.values
        for mutant in offspring:
            # mutate an individual with probability MUTPB
            if random.random() < mut_pb:
                toolbox.mutate(mutant)
                del mutant.fitness.values
        # Evaluate the individuals with an invalid fitness
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit
        print("  Evaluated %i individuals" % len(invalid_ind))
        # The population is entirely replaced by the offspring
        pop[:] = offspring
        # Gather all the fitnesses in one list and print the stats
        fits = [ind.fitness.values[0] for ind in pop]
        length = len(pop)
        if length != 0:
            mean = sum(fits) / length
            sum2 = sum(x * x for x in fits)
            std = abs(sum2 / length - mean ** 2) ** 0.5
            print("  Min %s" % min(fits))
            print("  Max %s" % max(fits))
            print("  Avg %s" % mean)
            print("  Std %s" % std)
    print("-- End of (successful) evolution --")
    best_solution = tools.selBest(pop, 1)
    if len(best_solution)>0:
        best_ind = tools.selBest(pop, 1)[0]
        print("Best individual is %s, %s" % (best_ind, best_ind.fitness.values))


def main():
    random.seed(3)
    popSize = 1000
    cxPb = 0.5
    mutPb = 0.2
    NGen = 100
    # Global creation of the individuals for GA
    ga_vrptw(
        ind_size=indSize,
        pop_size=popSize,
        cx_pb=cxPb,
        mut_pb=mutPb,
        gen_size=NGen
    )


if __name__ == '__main__':
    pool = multiprocessing.Pool(32)
    toolbox.register("map", pool.map)
    tic = timer()
    main()
    print('Computing Time: %s' % (timer() - tic))
    pool.close()
    # 测试
    # gene = [5, 4, 4, 20, 16, 12, 14, 9, 17, 10, 17, 10, 9, 10, 19, 17, 2, 10, 3, 7]
    # gene = [3, 6, 6, 10, 2, 4, 4, 5, 7, 10]
    # total_time = genes_to_time(gene)
    # print(total_time)
